import copy


class Solution(object):
    def largestMagicSquare(self, grid):
        m = len(grid)
        n = len(grid[0])
        h_grid = copy.deepcopy(grid)
        v_grid = copy.deepcopy(grid)
        l_grid = copy.deepcopy(grid)
        r_grid = copy.deepcopy(grid)
        for i in range(m):
            for j in range(n):
                if j > 0:
                    h_grid[i][j] += h_grid[i][j - 1]
                if i > 0:
                    v_grid[i][j] += v_grid[i - 1][j]
                if i > 0 and j > 0:
                    l_grid[i][j] += l_grid[i - 1][j - 1]
                if i > 0 and j < n - 1:
                    r_grid[i][j] += r_grid[i - 1][j + 1]
        max_k = min(m, n)
        for k in range(max_k, 0, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if i == 0:
                        base = v_grid[i + k - 1][j]
                    else:
                        base = v_grid[i + k - 1][j] - v_grid[i - 1][j]
                    flag = True
                    for z in range(k):
                        if i == 0:
                            if v_grid[i + k - 1][j + z] != base:
                                flag = False
                                break
                        else:
                            if v_grid[i + k - 1][j + z] - v_grid[i - 1][j + z] != base:
                                flag = False
                                break
                        if j == 0:
                            if h_grid[i + z][j + k - 1] != base:
                                flag = False
                                break
                        else:
                            if h_grid[i + z][j + k - 1] - h_grid[i + z][j - 1] != base:
                                flag = False
                                break
                    if flag:
                        if i == 0 or j == 0:
                            if l_grid[i + k - 1][j + k - 1] != base:
                                flag = False
                        else:
                            if l_grid[i + k - 1][j + k - 1] - l_grid[i - 1][j - 1] != base:
                                flag = False
                        if i == 0 or j == n - k:
                            if r_grid[i + k - 1][j] != base:
                                flag = False
                        else:
                            if r_grid[i + k - 1][j] - r_grid[i - 1][j + k] != base:
                                flag = False
                    if flag:
                        return k


data = Solution()
grid = [[1, 2, 1, 1], [2, 1, 1, 1], [3, 2, 2, 3], [1, 3, 3, 3]]
print(data.largestMagicSquare(grid))
